package 算法.NiuKe.JZ;

/**
 * @author:谢君臣
 * @Date:2021/4/1020:37
 * @version:1.0
 * @function: 把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。
 * 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。
 */
public class JZ33 {
    public static void main(String[] args) {

    }

    public int GetUglyNumber_Solution1(int index) {
        int[] a = new int[index + 1];
        int p2 = 1, p3 = 1, p5 = 1;
        a[1] = 1;
        for (int i = 2; i <= index; i++) {
            int num2 = a[p2] * 2, num3 = a[p3] * 3, num5 = a[p5] * 5;
            int num = Math.min(num5, Math.min(num2, num3));
            if (num2 == num) p2++;
            if (num3 == num) p3++;
            if (num5 == num) p5++;
            a[i] = num;
        }
        return a[index];
    }

    public int GetUglyNumber_Solution(int index) {
        int N = 0;
        for (int i = 1; N < index; i++) {
            int temp = i;
            while (temp % 2 == 0) temp = temp / 2;
            while (temp % 3 == 0) temp = temp / 3;
            while (temp % 5 == 0) temp = temp / 5;
            if (temp == 1) N++;
            if (N == index) return i;
        }
        return 0;
    }
}
